/*
This files contains convinient helper functions that can be used when
defining benchmarks.

Add your helper functions here. They may be useful for others, too.
*/

#ifndef __juniper_productions__
#define __juniper_productions__

/*

The timing programs are almost directly taken from the articles:

Andrew Koenig and Barbara E. Moo, Performance: Myths, Measurements, 
and Morals, Part 5: How Not to Measure Execution Time, Journal of 
Object-Oriented Programming 13,1 (2000), 29-31, and 39.

Andrew Koenig and Barbara E. Moo, Performance: Myths, Measurements, 
and Morals, Part 6 Useful Measurements---Finally!, Journal of 
Object-Oriented Programming 13,2 (2000), 31-33.

*/

#include <ctime>
#include <cassert>
#include <vector>
#include <algorithm>
#include <iostream>

/* 

10 ms is a reasonable clock precision on most computers.
1 s should be relatively large compared to one tick.

*/

const clock_t reasonable_precision = CLOCKS_PER_SEC / 100;
const clock_t high_precision = 1 * CLOCKS_PER_SEC;

double clock_overhead() {
  clock_t k = clock();
  clock_t start, limit;

  // Wait for the clock to tick
  do  
    start = clock();
  while (start == k);

  // Interrogate the clock until it has advanced
  limit = start + reasonable_precision;

  unsigned long r = 0;
  while ((k = clock()) < limit)
    ++r;
  return double(k - start) / r;
}

/* 

90% of the outcomes differ from at most 20% from the median.

*/

const unsigned int factor = 10;
const unsigned int percent = 20;

template <typename functor>
double measure_same_object(functor f) {
  std::vector<double> mv;
  unsigned int trial = 0;
  double overhead = clock_overhead();
  
  do {
    ++trial;
    mv.reserve(mv.size() + 2 * factor);
    clock_t k = clock();
    clock_t start;

    do
      start = clock();
    while (start == k);

    for (unsigned int i = 2 * factor; i > 0; --i) {
      unsigned long calls = 0;
      unsigned long limit = 1;
      unsigned long clock_calls = 0;
      const clock_t clocklimit = start + reasonable_precision;
      clock_t t;
    
      do {
	while (calls < limit) {
	  f();
	  ++calls;
	}
	limit *= 2;
	++clock_calls;
      } while ((t = clock()) < clocklimit);

      clock_t stop;
      do
	++clock_calls;
      while ((stop = clock()) == t);

      double ticks = (double(stop - start) - (clock_calls * overhead)) / double(calls);
      double running_time = ticks / double(CLOCKS_PER_SEC);
      if (ticks >= high_precision) {
        return running_time;
      }
      mv.push_back(running_time);
      start = stop;
    }
    assert(mv.size() == trial * 2 * factor);
    std::sort(mv.begin(), mv.end());
    double median = (mv[trial * factor] + mv[trial * factor - 1]) / 2;
    if (mv[trial] > (median * (100.0 - percent)) / 100.0 && 
        mv[mv.size() - trial - 1] < (median * (100.0 + percent)) / 100.0)
      return median;
  } while (trial < 100);
  assert(false);
}

/* Unittest for timing routines

class spin {
public:
  spin(int n0): n(n0) {
  }
  void operator()() {
    int i = n;
    while (--i >= 0);
  }
private:
  int n;
};

int main() {
  
  for (int i = 20; i < 100; ++i) {
    double time = measure_same_object(spin(i));
    std::cout << "i = " << i << ": " << time << std::endl;
  }
}

*/
#endif // __juniper_productions__






